package tianhao.luo.avl;

/**
 * @author: tianhao.luo@hand-china.com 2021/6/27  上午9:26
 */
public class Node {
    public int value;

    public Node left;

    public Node right;

    public Node(int value) {
        this.value = value;
    }

    // 添加结点的方法

    /**
     * 添加结点的方法
     * @param node 结点
     */
    public void add(Node node){
        if (node == null){
            return;
        }

        // 判断传入的结点和根节点的支
        if (node.value<this.value){
            // 当前结点的左子节点为null
            if (this.left == null){
                this.left = node;
            }else {
                // 递归向左子树添加
                this.left.add(node);
            }
        }

        if (node.value>=this.value){
            // 当前结点的右子节点为null
            if (this.right == null){
                this.right = node;
            }else {
                this.right.add(node);
            }
        }

        // 当添加完一个结点后,如果:右子树高度-左子树高度 >1,左旋转
        if (rightHeight() - lefHeight() >1){
            // 如果它的右子树的左子树的高度大于它的右子树高度
            if (right != null && right.lefHeight() > right.rightHeight()){
                // 对右子节点进行右旋转
                right.rightRotate();;
                // 对当前结点进行左旋转
                leftRotate();
            }else {
                leftRotate();
            }
            // 此处已经将平衡二叉树处理完成,无需再继续处理了
            return;
        }
        // 当添加完一个结点后,如果(左子树的高度-右子树的高度)>1,右旋转
        if (lefHeight() - rightHeight() >1){
            // 如果它的左子树的右子树高度大于它的左子树的高度
            if (left != null && left.rightHeight() > left.lefHeight()){
                // 先对当前结点的左结点(左子树)=>左旋转
                left.lefHeight();
                // 再对当前结点进行右旋转
                rightRotate();
            }else {
                rightRotate();
            }
        }
    }

    public void infixOrder(){
        if (this.left !=null){
            this.left.infixOrder();
        }

        System.out.println(this);

        if (this.right !=null){
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("Node{");
        sb.append("value=").append(value);
        sb.append('}');
        return sb.toString();
    }


    /**
     * 查找要删除的结点
     * @param value 需要删除的结点的值
     * @return 如果找到返回该结点,否则返回null
     */
    public Node searchNode(int value){
        // 找到该节点
        if (value == this.value){
            return this;
        }else if (value < this.value){
            // 查找的值小于当前结点的值
            // 需要左子树递归查找
            // 如果左子节点为空
            if (this.left == null){
                return null;
            }
            return this.left.searchNode(value);
        }else {
            // 如果查找的值不小于当前节点,向右子树递归查找
            if (this.right == null){
                return null;
            }
            return this.right.searchNode(value);
        }
    }


    /**
     * 查找要删除结点的父节点
     * @param value 要删除的结点值
     * @return 返回父节点
     */
    public Node searchParent(int value){
        // 当前结点是否为父节点
        if (this.left !=null && this.left.value==value){
            return this;
        }else if (this.right !=null && this.right.value ==value){
            return this;
        }else {
            // 查找的值小于当前结点的值,并且当前结点的左子节点不为空
            if (value < this.value && this.left !=null){
                return this.left.searchParent(value);
            }else if (value >= this.value && this.right !=null){
                return this.right.searchParent(value);
            }else {
                // 没有找到父节点
                return null;
            }
        }
    }

    // 返回以当前结点为根节点的树的高度
    public int height(){
        return Math.max(left == null ? 0 :left.height(),right == null ? 0:right.height()) + 1;
    }

    // 返回左子树的高度
    public int lefHeight(){
        if (left == null){
            return 0;
        }
        return left.height();
    }

    // 返回右子树的高度
    public int rightHeight(){
        if (right == null){
            return 0;
        }
        return right.height();
    }


    /**
     * 左旋转
     * 用于在添加结点的过程中
     */
    private void leftRotate(){
        // 1. 创建新的结点,以根节点创建
        Node node = new Node(value);
        // 2. 把新的结点的左子树设置为当前结点的左子树
        node.left = left;
        // 3. 把新的结点的右子树设置成当前结点的右子树的左子树
        node.right = right.left;
        // 把当前结点的值,替换为右子结点的值
        value = right.value;
        // 把当前结点的右子树设置成当前结点的右子树的右子树
        right = right.right;
        // 把当前结点的左子节点设置成新的结点
        left = node;
    }

    /**
     * 右旋转
     */
    public void rightRotate(){
        Node node = new Node(value);
        node.right = right;
        node.left = left.right;
        value = left.value;
        left = left.left;
        right = node;
    }
}
